package lbj.cyw.dp;
/*
* 最大子数组和
*
* */
public class MaxSubArray53 {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        if(n==1){
            return nums[0];
        }
        int[] dp=new int[n];
        int max=dp[0];
        for(int i=1;i<n;i++){
            dp[i]=dp[i-1]<0?nums[i]:dp[i-1]+nums[i];
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}
